{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Upside Down"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: upsideDownBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #上下翻转二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ，请你将此二叉树上下翻转，并返回新的根节点。</p>\n",
    "\n",
    "<p>你可以按下面的步骤翻转一棵二叉树：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>原来的左子节点变成新的根节点</li>\n",
    "\t<li>原来的根节点变成新的右子节点</li>\n",
    "\t<li>原来的右子节点变成新的左子节点</li>\n",
    "</ol>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/29/main.jpg\" style=\"width: 600px; height: 95px;\" />\n",
    "<p>上面的步骤逐层进行。题目数据保证每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/29/updown.jpg\" style=\"width: 800px; height: 161px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[4,5,2,null,null,3,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 10]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10</code></li>\n",
    "\t<li>树中的每个右节点都有一个同级节点（即共享同一父节点的左节点）</li>\n",
    "\t<li>树中的每个右节点都没有子节点</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-upside-down](https://leetcode.cn/problems/binary-tree-upside-down/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-upside-down](https://leetcode.cn/problems/binary-tree-upside-down/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.rs = None\n",
    "        \n",
    "    def traverse(self, root):\n",
    "        if not root.left:\n",
    "            self.rs = TreeNode(root.val)\n",
    "            rs = self.rs\n",
    "            return rs\n",
    "        else:\n",
    "            rs = self.traverse(root.left)\n",
    "            if root.right:\n",
    "                rs.left = TreeNode(root.right.val)\n",
    "            rs.right = TreeNode(root.val)\n",
    "\n",
    "        return rs.right\n",
    "    \n",
    "    def upsideDownBinaryTree(self,root):\n",
    "        if not root:\n",
    "            return None\n",
    "        if not root.left:\n",
    "            return root\n",
    "        self.traverse(root)\n",
    "        return self.rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left:\n",
    "            return root\n",
    "        \n",
    "        prev = root\n",
    "        curr = root.left\n",
    "        rc = root.right\n",
    "\n",
    "        root.left = None\n",
    "        root.right = None\n",
    "\n",
    "        while curr:\n",
    "            p, q = curr.left, curr.right\n",
    "            curr.right = prev\n",
    "            curr.left = rc\n",
    "\n",
    "            curr, prev, rc = p, curr, q\n",
    "            \n",
    "\n",
    "        return prev\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        left = None\n",
    "        right = None\n",
    "        while root:\n",
    "            rootleft = root.left\n",
    "            rootright = root.right\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            left = rootright\n",
    "            right = root\n",
    "            root = rootleft\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        left = None\n",
    "        right = None\n",
    "        while root:\n",
    "            rootleft = root.left\n",
    "            rootright = root.right\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            left = rootright\n",
    "            right = root\n",
    "            root = rootleft\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        parent = None\n",
    "        parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            \n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None or root.left is None:\n",
    "            return root\n",
    "\n",
    "        left=root.left\n",
    "        right=root.right\n",
    "        node=self.upsideDownBinaryTree(root.left)\n",
    "        root.left=root.right=None\n",
    "        left.left=right\n",
    "        left.right=root\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        left = None\n",
    "        right = None\n",
    "        while root:\n",
    "            rootleft = root.left\n",
    "            rootright = root.right\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            left = rootright\n",
    "            right = root\n",
    "            root = rootleft\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        left = None\n",
    "        right = None\n",
    "        while root:\n",
    "            rootleft = root.left\n",
    "            rootright = root.right\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            left = rootright\n",
    "            right = root\n",
    "            root = rootleft\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        parent=parent_right=None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None ###\n",
    "        while root:\n",
    "            root_left = root.left \n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "#         if not root or not root.left:\n",
    "#             return root\n",
    "#         tmpL, tmpR = root.left, root.right\n",
    "#         res = self.upsideDownBinaryTree(root.left)\n",
    "#         root.left = root.right = None\n",
    "#         tmpL.left = tmpR\n",
    "#         tmpL.right = root\n",
    "#         return res\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/binary-tree-upside-down/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "#class Solution:\n",
    "    # def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "    #     if not root or not root.left:\n",
    "    #         return root\n",
    "\n",
    "    #     while root.left:\n",
    "    #         #root_left=root.left\n",
    "    #         tmpL, tmpR = root.left, root.right\n",
    "    #     #   res = self.upsideDownBinaryTree(root.left)\n",
    "    #         root.left = root.right = None #### 你这个相当于把上一步改好的消解掉了，所以必须从下往上改！！！ \n",
    "    #         tmpL.left = tmpR\n",
    "    #         tmpL.right = root\n",
    "    #         root=tmpL\n",
    "    #     return root\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root or not root.left:\n",
    "            return root\n",
    "        tl,tr=root.left,root.right\n",
    "        res=self.upsideDownBinaryTree(root.left)\n",
    "        root.left=root.right=None\n",
    "        tl.left=tr\n",
    "        tl.right=root\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def walk_tree(node, ll):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ll.append(node.val)\n",
    "                return \n",
    "            if node.left:\n",
    "                walk_tree(node.left, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            if node.right:\n",
    "                walk_tree(node.right, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            ll.append(node.val)\n",
    "\n",
    "        ll = []\n",
    "        walk_tree(root, ll)\n",
    "\n",
    "        def build(ll1):\n",
    "            if len(ll1) == 0:\n",
    "                return\n",
    "            if len(ll1) == 1:\n",
    "                return TreeNode(ll1[0])\n",
    "            cur = TreeNode(ll1[0])\n",
    "            if ll1[1] != -1:\n",
    "                cur.left = TreeNode(ll1[1])\n",
    "            else:\n",
    "                cur.left = None\n",
    "            right = build(ll1[2:])\n",
    "            cur.right = right\n",
    "            return cur\n",
    "        return build(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        node = root\n",
    "        while node.left:\n",
    "            node = node.left\n",
    "        new_head = node\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            # left = dfs(root.left)\n",
    "            # right = dfs(root.right)\n",
    "            # if left:\n",
    "            #     left.left = right\n",
    "            #     left.right = root\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                right = root.right\n",
    "                left.left = right\n",
    "                left.right = root\n",
    "                root.right = None\n",
    "                root.left = None\n",
    "            return root\n",
    "        \n",
    "        dfs(root)\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left:\n",
    "            return root    \n",
    "        \n",
    "        leftnode = root.left   \n",
    "        rightnode = root.right  \n",
    "\n",
    "        res = self.upsideDownBinaryTree(root.left)\n",
    "\n",
    "        root.left = root.right = None   \n",
    "\n",
    "        leftnode.left = rightnode\n",
    "        leftnode.right = root   \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        if not root.left:\n",
    "            return root\n",
    "        tmp_left=None\n",
    "        tmp_right=None\n",
    "        last=None\n",
    "        cnt=0\n",
    "        while root.left:\n",
    "            current=TreeNode(root.left.val)\n",
    "            if cnt!=0:\n",
    "                current.right=last\n",
    "            else:\n",
    "                current.right=TreeNode(root.val)\n",
    "            if root.right:\n",
    "                current.left=TreeNode(root.right.val)\n",
    "            last=current\n",
    "            root=root.left\n",
    "            cnt+=1\n",
    "        return last\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def process(node):\n",
    "            if not node: return\n",
    "\n",
    "            n = process(node.left)\n",
    "            process(node.right)\n",
    "\n",
    "            if node.left:\n",
    "                node.left.left = node.right\n",
    "                node.left.right = node\n",
    "\n",
    "            n = node if not n else n\n",
    "            node.left = None\n",
    "            node.right = None\n",
    "\n",
    "            return n\n",
    "\n",
    "        return process(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node or not node.left:\n",
    "                return node\n",
    "\n",
    "            _n = dfs(node.left)\n",
    "\n",
    "            left, right = node.left, node.right\n",
    "            left.left, left.right = right, node\n",
    "            node.left, node.right = None, None\n",
    "\n",
    "            return _n\n",
    "           \n",
    "\n",
    "        \n",
    "        return dfs(root)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.judge=0\n",
    "\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        if root.left==None and root.right==None:\n",
    "            if self.judge==0:\n",
    "                self.judge=root\n",
    "            return root\n",
    "        self.upsideDownBinaryTree(root.left)\n",
    "        root.left.left=root.right\n",
    "        root.left.right=root\n",
    "        root.left=None\n",
    "        root.right=None\n",
    "        # if self.judge!=0:\n",
    "        return self.judge\n",
    "        # return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def transTree(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            elif (root.left is None) and (root.right is None):\n",
    "                return root, root\n",
    "            \n",
    "            # print(root.val)\n",
    "            ll, lr = transTree(root.left)\n",
    "            rl, rr = transTree(root.right)\n",
    "            \n",
    "            lr.right = root\n",
    "            lr.left = rr\n",
    "            root.left, root.right = None, None\n",
    " \n",
    "            return ll, root\n",
    "        \n",
    "        new_root, _ = transTree(root)\n",
    "        return new_root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        parent = None\n",
    "        parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            \n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.judge=0\n",
    "\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        if root.left==None and root.right==None:\n",
    "            if self.judge==0:\n",
    "                self.judge=root\n",
    "            return root\n",
    "        self.upsideDownBinaryTree(root.left)\n",
    "        root.left.left=root.right\n",
    "        root.left.right=root\n",
    "        root.left=None\n",
    "        root.right=None\n",
    "        # if self.judge!=0:\n",
    "        return self.judge\n",
    "        # return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        ans = None\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right and ans is None:\n",
    "                ans = root\n",
    "                return\n",
    "            left = root.left\n",
    "            right = root.right\n",
    "            root.left = None\n",
    "            root.right = None\n",
    "            dfs(left)\n",
    "            left.left = right\n",
    "            left.right = root\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left: \n",
    "            return root \n",
    "        new_root = self.upsideDownBinaryTree(root.left)\n",
    "        if root.left:\n",
    "            root.left.left = root.right \n",
    "            root.left.right = root \n",
    "            root.left = root.right = None \n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left :\n",
    "            return  root\n",
    "\n",
    "        left,right =root.left,root.right\n",
    "        newroot =self.upsideDownBinaryTree(root.left)\n",
    "        left.left =right\n",
    "        left.right =root\n",
    "        root.left=root.right =None\n",
    "        return newroot\n",
    "\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "      if not root:\n",
    "        return\n",
    "\n",
    "      def flip(node, left, right):\n",
    "        if not left:\n",
    "          return node\n",
    "\n",
    "        node.left = None\n",
    "        node.right = None\n",
    "        root = flip(left, left.left, left.right)\n",
    "        left.left = right\n",
    "        left.right = node\n",
    "        return root\n",
    "\n",
    "      return flip(root, root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node):\n",
    "            if not node.left:\n",
    "                return node\n",
    "            newRoot = dfs(node.left)\n",
    "            node.left.left = node.right\n",
    "            node.left.right = node\n",
    "            node.left = node.right = None\n",
    "            return newRoot \n",
    "        if not root:\n",
    "            return None\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or (not root.left and not root.right):\n",
    "            return root\n",
    "        \n",
    "        res = self.upsideDownBinaryTree(root.left)\n",
    "        \n",
    "        root.left.left = root.right \n",
    "        root.left.right = root\n",
    "\n",
    "        root.left, root.right = None, None\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        left = None\n",
    "        right = None\n",
    "        while root:\n",
    "            rootleft = root.left\n",
    "            rootright = root.right\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            left = rootright\n",
    "            right = root\n",
    "            root = rootleft\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root or not root.left:\r\n",
    "            return root\r\n",
    "        tmpL = root.left\r\n",
    "        tmpR = root.right\r\n",
    "        res = self.upsideDownBinaryTree(root.left)\r\n",
    "        root.left = root.right = None\r\n",
    "        tmpL.right = root\r\n",
    "        tmpL.left = tmpR\r\n",
    "        return res\r\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root or not root.left:\r\n",
    "            return root\r\n",
    "        tmpL = root.left\r\n",
    "        tmpR = root.right\r\n",
    "        res = self.upsideDownBinaryTree(root.left)\r\n",
    "        root.left = root.right = None\r\n",
    "        tmpL.right = root\r\n",
    "        tmpL.left = tmpR\r\n",
    "        return res\r\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        '''\n",
    "                    1\n",
    "                2       3\n",
    "            4         5     6\n",
    "        '''\n",
    "        # parent = parent_right = None\n",
    "        # while root:\n",
    "        #     parent_left = root.left\n",
    "        #     root.left = parent_right\n",
    "        #     parent_right = root.right\n",
    "        #     root.right = parent\n",
    "        #     parent = root\n",
    "        #     root = parent_left\n",
    "        # return parent\n",
    "        if not root or not root.left:\n",
    "            return root\n",
    "        tmpl = root.left\n",
    "        tmpr = root.right\n",
    "        result = self.upsideDownBinaryTree(root.left)\n",
    "        root.left = None\n",
    "        root.right = None\n",
    "        tmpl.right = root\n",
    "        tmpl.left = tmpr\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left: \n",
    "            return root \n",
    "        new_root = self.upsideDownBinaryTree(root.left)\n",
    "        if root.left:\n",
    "            root.left.left = root.right \n",
    "            root.left.right = root \n",
    "            root.left = root.right = None \n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root):\n",
    "        if not root:\n",
    "            return root\n",
    "        if not root.left and not root.right:\n",
    "            return root\n",
    "        leftnode = root.left\n",
    "        newhead = self.upsideDownBinaryTree(root.left)\n",
    "        leftnode.left = root.right\n",
    "        leftnode.right = root\n",
    "        root.left = None\n",
    "        root.right = None\n",
    "        return newhead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root or not root.left: \n",
    "            return root \n",
    "        \n",
    "        res = self.upsideDownBinaryTree(root.left)\n",
    "        if root.left:\n",
    "            root.left.left = root.right \n",
    "            root.left.right = root \n",
    "            root.left = None \n",
    "            root.right = None \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        cur = root\n",
    "        parent, sibling = None, None\n",
    "        while cur:\n",
    "            left, right = cur.left, cur.right\n",
    "            cur.left = sibling\n",
    "            cur.right = parent\n",
    "            parent, sibling = cur, right\n",
    "            cur = left\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def walk_tree(node, ll):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ll.append(node.val)\n",
    "                return \n",
    "            if node.left:\n",
    "                walk_tree(node.left, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            if node.right:\n",
    "                walk_tree(node.right, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            ll.append(node.val)\n",
    "\n",
    "        ll = []\n",
    "        walk_tree(root, ll)\n",
    "        print(ll)\n",
    "\n",
    "        def build(ll1):\n",
    "            if len(ll1) == 0:\n",
    "                return\n",
    "            if len(ll1) == 1:\n",
    "                return TreeNode(ll1[0])\n",
    "            cur = TreeNode(ll1[0])\n",
    "            if ll1[1] != -1:\n",
    "                cur.left = TreeNode(ll1[1])\n",
    "            else:\n",
    "                cur.left = None\n",
    "            right = build(ll1[2:])\n",
    "            cur.right = right\n",
    "            return cur\n",
    "        return build(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        parent = parent_right = None\n",
    "        while root:\n",
    "            root_left = root.left\n",
    "            root.left = parent_right\n",
    "            parent_right = root.right\n",
    "            root.right = parent\n",
    "            parent = root\n",
    "            root = root_left\n",
    "        return parent\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "#         if not root or not root.left:\n",
    "#             return root\n",
    "#         tmpL, tmpR = root.left, root.right\n",
    "#         res = self.upsideDownBinaryTree(root.left)\n",
    "#         root.left = root.right = None\n",
    "#         tmpL.left = tmpR\n",
    "#         tmpL.right = root\n",
    "#         return res\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/binary-tree-upside-down/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def walk_tree(node, ll):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ll.append(node.val)\n",
    "                return \n",
    "            if node.left:\n",
    "                walk_tree(node.left, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            if node.right:\n",
    "                walk_tree(node.right, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            ll.append(node.val)\n",
    "\n",
    "        ll = []\n",
    "        walk_tree(root, ll)\n",
    "\n",
    "        def build(ll1):\n",
    "            if len(ll1) == 0:\n",
    "                return\n",
    "            if len(ll1) == 1:\n",
    "                return TreeNode(ll1[0])\n",
    "            cur = TreeNode(ll1[0])\n",
    "            if ll1[1] != -1:\n",
    "                cur.left = TreeNode(ll1[1])\n",
    "            else:\n",
    "                cur.left = None\n",
    "            right = build(ll1[2:])\n",
    "            cur.right = right\n",
    "            return cur\n",
    "        return build(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def walk_tree(node, ll):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ll.append(node.val)\n",
    "                return \n",
    "            if node.left:\n",
    "                walk_tree(node.left, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            if node.right:\n",
    "                walk_tree(node.right, ll)\n",
    "            else:\n",
    "                ll.append(-1)\n",
    "            ll.append(node.val)\n",
    "\n",
    "        ll = []\n",
    "        walk_tree(root, ll)\n",
    "\n",
    "        def build(ll1):\n",
    "            if len(ll1) == 0:\n",
    "                return\n",
    "            if len(ll1) == 1:\n",
    "                return TreeNode(ll1[0])\n",
    "            cur = TreeNode(ll1[0])\n",
    "            if ll1[1] != -1:\n",
    "                cur.left = TreeNode(ll1[1])\n",
    "            else:\n",
    "                cur.left = None\n",
    "            right = build(ll1[2:])\n",
    "            cur.right = right\n",
    "            return cur\n",
    "        return build(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def transTree(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            elif (root.left is None) and (root.right is None):\n",
    "                return root, root\n",
    "            \n",
    "            print(root.val)\n",
    "            ll, lr = transTree(root.left)\n",
    "            rl, rr = transTree(root.right)\n",
    "            \n",
    "            lr.right = root\n",
    "            lr.left = rr\n",
    "            root.left, root.right = None, None\n",
    " \n",
    "            return ll, root\n",
    "        \n",
    "        new_root, _ = transTree(root)\n",
    "        return new_root\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
